
// 替换最小子串长度
public class MinimumReplacementSubstringLength {
    public static int solution(String input) {
        int n = input.length();
        if (n % 4 != 0) {
            return -1; // 输入长度不是4的倍数
        }

        int targetFreq = n / 4;
        int[] freq = new int[4];

        // 计算初始频率
        for (char c : input.toCharArray()) {
            freq[getIndex(c)]++;
        }

        // 如果已经平衡，不需要替换
        if (freq[0] == targetFreq && freq[1] == targetFreq && freq[2] == targetFreq && freq[3] == targetFreq) {
            return 0;
        }

        // 尝试所有可能的子串长度
        for (int len = 1; len <= n; len++) {
            for (int start = 0; start + len <= n; start++) {
                int[] newFreq = freq.clone();
                // 移除子串中的字符
                for (int i = start; i < start + len; i++) {
                    newFreq[getIndex(input.charAt(i))]--;
                }
                // 检查是否可以通过添加字符使频率平衡
                int needed = 0;
                for (int f : newFreq) {
                    needed += Math.max(0, targetFreq - f);
                }
                if (needed == len) {
                    return len;
                }
            }
        }

        return -1; // 如果无法找到解决方案
    }

    private static int getIndex(char c) {
        switch (c) {
            case 'A': return 0;
            case 'S': return 1;
            case 'D': return 2;
            case 'F': return 3;
            default: return -1;
        }
    }

    public static void main(String[] args) {
        System.out.println(solution("ADDF") == 1);
        System.out.println(solution("ASAFASAFADDD") == 3);
    }
}